TST switching fabrics are commonly used to reduce physical complexity in time division multiplexed (TDM) switching systems. An n-port, m-timeslot TST switching fabric receives a different input signal at each one of the fabric's n ingress ports. Each input signal is time-divided into “timeslots.” Each timeslot contains a discrete “grain” portion of the input signal. The switching fabric's input time stage permits arbitrary temporal rearrangement of the input signal by reassigning ingress grains to different timeslots. The temporally rearranged signal then passes through a space stage which permits arbitrary space rearrangement of the input signal by reassigning grains to different ports. An output time stage then permits further arbitrary temporal rearrangement of the space-permuted signal by reassigning egress grains to different timeslots. TST switching fabrics thus permit any signal grain received on any input port in any timeslot to be output on any output port in any timeslot.
For example, FIG. 1A depicts a simple 3 port, 4 timeslot TST switching fabric. In the particular situation depicted in FIG. 1A, input port 1 has received an input signal consisting of grain A assigned to ingress timeslot 1, grain B assigned to ingress timeslot 2, grain C assigned to ingress timeslot 3 and grain D assigned to ingress timeslot 4; and, the input time stage has temporally rearranged the port 1 signal by reassigning grain D to egress timeslot 1 and reassigning grain A to egress timeslot 4. Grains B and C remain assigned to timeslots 2 and 3 respectively.
Input port 2 has received an input signal consisting of grain E assigned to ingress timeslot 1, grain F assigned to ingress timeslot 2, grain G assigned to ingress timeslot 3 and nothing assigned to ingress timeslot 4. The input time stage has temporally rearranged the port 2 signal by reassigning grain G to egress timeslot 1, reassigning grain E to egress timeslot 3 and reassigning grain F to egress timeslot 4. The input time stage has taken advantage of the fact that no grain occupies ingress timeslot 4 by replicating grain G in egress timeslot 2 so that grain G is assigned to two egress timeslots. The input time stage's reassignment of grains to timeslots does not affect the port assignments.
Input port 3 has received an input signal consisting of grain H assigned to ingress timeslot 1, grain I assigned to ingress timeslot 2, and nothing assigned to either of ingress timeslots 3 or 4. The input time stage has temporally rearranged the port 3 signal by reassigning grain H to egress timeslot 4 and reassigning grain I to egress timeslot 3.
In the particular situation depicted in FIG. 1A, the space stage has space-permuted the signal received from the input time stage by reassigning grain D from port 1 to port 3, reassigning grain C from port 1 to port 2, and reassigning grain A from port 1 to port 3. Grain B remains assigned to port 1. The space stage has taken advantage of the fact that no grain occupies port 3's timeslot 2 by replicating grain B in port 2 in timeslot 2 so that grain B is assigned to two ports in timeslot 2. The space stage's reassignment of grains to ports does not affect the timeslot assignments.
With respect to port 2, the space stage has taken advantage of the fact that no grain occupies port 3's egress timeslot 1 by replicating grain G in port 1 in timeslot 1 so that grain G is assigned to two ports in timeslot 1. The space stage has also reassigned grain G in timeslot 2 from port 2 to port 3, reassigned grain E from port 2 to port 1, and reassigned grain F from port 2 to port 1.
With respect to port 3, the space stage has reassigned grain H from port 3 to port 2. Grain I remains assigned to port 2.
The output time stage has then temporally rearranged the port 1 signal by reassigning grain G from ingress timeslot 1 to egress timeslot 4, reassigning grain B from ingress timeslot 2 to egress timeslot 3, reassigning grain E from ingress timeslot 3 to egress timeslot 1, and reassigning grain F from ingress timeslot 4 to egress timeslot 2.
With respect to port 2, the output time stage has temporally reassigned grain G from ingress timeslot 1 to egress timeslot 2, reassigned grain B from ingress timeslot 2 to egress timeslot 1, reassigned grain C from ingress timeslot 3 to egress timeslot 4, and reassigned grain H from ingress timeslot 4 to egress timeslot 3.
With respect to port 3, the output time stage has temporally reassigned grain D from ingress timeslot 1 to egress timeslot 3, reassigned grain G from ingress timeslot 2 to egress timeslot 4, reassigned grain I from ingress timeslot 3 to egress timeslot 2, and reassigned grain A from ingress timeslot 4 to egress timeslot 1.
It can thus be seen that, for the particular situation depicted in FIG. 1A, every signal grain is reassigned for output on a different port and in a different timeslot than that grain's input port and timeslot.
A switching fabric is “non-blocking” if every possible combination of input signals can be mapped successfully from the switch's input ports to the switch's output ports. A switching fabric is “rearrangeably non-blocking” if, regardless of the fabric's current assignment of grains to ports and timeslots, some reassignment (i.e. rearrangement) will enable successful mapping of every possible combination of input signals from the switch's input ports to the switch's output ports. A switch, also known as a crossbar switch, can be made strictly non-blocking—non-blocking with no need for rearrangement—by providing additional hardware elements. For example, if each output grain can receive input from any input grain, then non-blocking non-rearranging switching is possible at the cost of at least n2 m2 hardware elements, where n is the number of ports and m is the number of timeslots since one crosspoint switch is required for each output port and timeslot multiplied by each input port and timeslot. In contrast, TST switching fabrics require only n2+2nm2 hardware elements to achieve non-blocking performance, a significant hardware savings.
Unlike crossbar switches which are non-rearrangeably non-blocking for multicast, TST switching fabrics are only rearrangeably non-blocking for unicast traffic loads; that is, loads in which no ingress grain is scheduled for output on more than one egress port. TST switching fabrics (without speedup as discussed below) are blocking for arbitrary multicast traffic loads; that is, loads in which at least one ingress grain is scheduled for output on two or more different egress ports, as in the FIG. 1A example where port 1 ingress grain B is scheduled for so-called 2-cast output on ports 1 and 2; and, port 2 ingress grain G is scheduled for so-called 3-cast output on ports 1, 2 and 3. Multicasting can be implemented by means of input port replication, namely by replicating ingress grains in the input time stage and unicasting each such replication through the space stage, as previously explained in the case of grain G. This approach can be non-blocking within the space stage, but requires excess capacity at the ingress port to accept the replicated grains. For example, in the situation depicted in FIG. 1A, grain G could not have been replicated on port 2 by the input time stage if ingress timeslot 4 had contained a grain. Such excess capacity is often unavailable.
Because TST switching fabrics are rearrangeably non-blocking for unicast traffic it is always possible to arrange a schedule for any set of unicast requests in which there will be no space stage scheduling conflicts; that is, no situation in which 2 grains are assigned to the same port in the same timeslot. TST switching fabrics can be made strictly (non-rearrangeably) non-blocking for unicast by introducing a so-called “speedup” feature. This can be done in several ways. One method, illustrated in FIG. 16, is to increase the number of timeslots in the input time stage so that, for example, m timeslots received by the input time stage are presented to the space stage as 2m timeslots, with the 2m timeslots presented by the space stage to the output time stage being reduced by the output time stage to m timeslots for output. The FIG. 16 switching fabric's space stage must run twice as fast as the FIG. 1A switching fabric's space stage to support the FIG. 16 fabric's 2-times speedup relative to the FIG. 1A fabric.
Another speedup technique, illustrated in FIG. 17, is to increase the number of ports, for example by doubling the width of the space stage, with the input time stage presenting each timeslot to the space stage twice to achieve 2m timeslots in the space stage, followed by a corresponding 2:1 reduction of timeslots in the output time stage. The FIG. 17 switching fabric's time stages must manage two independently time-arranged sets of grains for each input and output port to support the FIG. 17 fabric's 2-times speedup relative to the FIG. 1A fabric.
A complete description of a TST switching fabric depends not only on the fabric's number of external ports and external timeslots, but also on the fabric's number of internal ports and timeslots. Any TST switching fabric can be characterized as having n external ports, m external timeslots, m1 input time stage ingress (i.e. internal) timeslots, m, output time stage egress (i.e. internal) timeslots, m2 input time stage egress (i.e. internal) timeslots and m2 output time stage ingress (i.e. internal) timeslots. A fabric's time stage speedup factor, it, is expressed as a ratio of the number of internal to external time stage timeslots: it=m2/m. If a fabric has no time stage speedup, m2=m. In other words, that fabric exhibits unity time stage speedup (i.e. it=1). FIG. 1A depicts a fabric for which it=1, since m2/m=4/4=1 for that fabric. The FIG. 16 fabric has 2-times speedup relative to the FIG. 1A fabric; meaning it=2 for the FIG. 16 fabric, since m2/m=8/4=2 for the FIG. 16 fabric.
A fabric's space stage speedup factor, is, is expressed as a ratio of the number of internal to external ports: is=p/n, where p is the number of internal ports. The space stage speedup factor indicates the number of ports, i.e. is, to which each input timeslot must supply input grains. FIG. 1A depicts a fabric for which is=1, since p/n=3/3=1 for that fabric. The FIG. 17 fabric has 2-times speedup relative to the FIG. 1A fabric; meaning it=2 for the FIG. 17 fabric, since p/n=6/3=2 for the FIG. 17 fabric.
For some applications, it and is simultaneously have values greater than 1. For some applications, it, or is, or both, simultaneously have values less than 1. In any case, a fabric's overall speedup factor, s, is expressed as s=it·is.
A TST switching fabric with 2-times speedup is strictly non-blocking for unicast loads. This can be understood by referring to FIG. 2, which depicts the 2m timeslots of a 2-times sped-up m-timeslot TST switching fabric in a worst case scheduling scenario with one group of m−1 timeslots in use by previous inputs from x and another group of m−1 timeslots in use by previous outputs at y, with no overlap between the two groups of timeslots. The total number of timeslots in use is thus m−1+m−1=2m−2 (i.e. all but 2 of the 2m available timeslots are in use). In other words, with 2-times speedup, even this worst case leaves 2 timeslots free for scheduling the last connection of a 100% load of unicast connection requests, namely a request for unicast connection of input x to output y.
Typically, there is some overlap in the scheduling of inputs and outputs, as shown in FIG. 3, where overlap between the previous scheduling of m−1 timeslots for input x and m−1 timeslots for output y leaves more than 2 timeslots free for scheduling.
Similarly, a TST switching fabric with 3-times speedup is strictly non-blocking for 2-cast loads. This can be understood by referring to FIG. 4, which depicts the 3m timeslots of a 3-times sped-up m-timeslot TST switching fabric in a worst case scheduling scenario with a first group of m−1 timeslots in use by previous inputs from x, a second group of m−1 timeslots in use by previous outputs at y and a third group of m−1 timeslots in use by previous outputs at z, with no overlap between the three groups of timeslots. The total number of timeslots in use is thus m−1+m−1+m−1=3m−3 (i.e. all but 3 of the 3m available timeslots are in use). In other words, with 3-times speedup, even this worst case leaves 3 timeslots free for scheduling the last connection of a 100% load of 2-cast connection requests, namely a request for 2-cast connection of input x to output y and to output z involving m timeslots.
Like unicast situations, 2-cast situations typically involve some overlap in the scheduling of the input and the outputs, leaving more than 3 free timeslots. The goal in multicast connection scheduling is to maximize scheduling efficiency to guarantee enough free timeslots to ensure the ability to schedule any requested multicast-up to the capability of the switching fabric, considering that a TST switching fabric may have inherent multicast limitations.
The unicast and multicast properties of TST switches have been investigated in the literature. The equivalence of various switching architectures is well known. For example, FIG. 1B shows the translation of the TST network of FIG. 1A into a so-called “Clos Network.” In this configuration, the initial time stages are translated into 4×4 crosspoint switches; the space stage is translated into 4 3×3 switches, and the final time stage is translated into 3 4×4 crosspoint switches. FIG. 1C shows a similar space:time:space (STS) switch. STS switches are the dual of TST switches, where an initial space stage feeds a second stage of time stages to order data for output after a final space stage. The STS switch can be translated to yield the equivalent Clos Network of FIG. 1D. This reveals that while the FIGS. 1A and 1C switches are similar, they are not the same: the initial space stage can only switch 3 elements per timeslot and this leads to a slightly different translation. This invention is applicable to any similar architecture.
More generally, a 2-cast connection request can be specified as X:(y→z, w) where X is the label of the connection that originates at port y and is received at outputs z and w. Connections are also known as “calls”. Call labels are analogous to grains. Thus, in FIG. 1A, each letter-labeled grain represents a different call. The set of inputs and outputs are disjoint. A call must originate at an input port and must terminate at one or more output ports. Typically, switching fabrics are symmetrical and have the same number of inputs as outputs, so both inputs and outputs are specified as numbers in the range of 1 to n where n is the number of ports. Labels are used to disambiguate calls, since two different calls can have the same input and output ports.
Graph theory can be used to reveal the most difficult multicast loads. In a multicast resource graph, each call is represented as a node. An “edge” connects nodes which represent a scheduling conflict in the sense that the calls represented by the connected nodes share at least one resource—an input port or output port, or both. FIG. 5 depicts a multicast resource graph corresponding to the set four connection requests A:(1→3, 4), B:(1→3, 5), C:(2→3, 5), and D:(2→5). The edge connecting nodes A and B is labeled “1, 3,” because calls A and B both use input port 1 and they both use output port 3. This represents two scheduling conflicts because an input port can service only one call and an output port can service only one call. The edge connecting nodes A and C reveals another scheduling conflict—the edge is labeled “3” because calls A and C both use output port 3. The edge connecting nodes B and C is labeled “3, 5” because calls B and C conflict in their usage of output port 3 and output port 5. The edge connecting nodes B and D reveals yet another scheduling conflict—the edge is labeled “5” because calls B and D both use output port 5. A still further scheduling conflict is revealed by the edge connecting nodes C and D, which is labeled “2” because calls C and D both use input port 2. No edge connects nodes A and D because calls A and D have no common input ports and no common output ports.
Graph “coloring” is the process of assigning colors to a graph's nodes such that no node is adjacent to another node having the same color. A “minimal” graph coloring uses the fewest colors. The FIG. 5 graph can be minimally 3-colored as shown in FIG. 6. Node A is “colored” by diagonal hatching, node B is “colored” by horizontal and vertical cross-hatching, node C is “colored” by the same diagonal hatching as node A and node D is “colored” by diagonal cross-hatching. The FIG. 5 graph can be 3-colored because calls A and D share no resources and can thus have the same color. Graph coloring can be related to call scheduling. Any calls corresponding to nodes having the same color can be scheduled in the same timeslot since such calls share no resources and thus have no input or output port conflicts.
FIG. 7 depicts a multicast resource graph corresponding to the set four connection requests A:(1→3, 4), B:(1→5, 6), C:(2→3, 5), and D:(2→4, 6). This graph represents a “clique”—a set of nodes in which each node is connected to every other node. A clique can be colored only by assigning a different color to each node. Thus, the FIG. 7 graph can be minimally 4-colored. Since each edge connecting the FIG. 7 nodes bears only one numeric label, it is apparent that each edge represents a scheduling conflict involving only one resource (i.e. an input port or and input port, but not both). Such a clique, which consumes the fewest resources, represents a challenging 2-cast load since it requires the most colors for coloring and hence the most timeslots for scheduling. Examination of the set of four connection requests reveals that each port is referenced exactly twice. Therefore, an equivalent set of non-conflicting calls can be scheduled by replicating each call m/2 times, where m is the number of timeslots, without over-allocating any input or output port. Such replication produces a clique having 2m nodes, since if 4 calls are each copied m/2 times, 2m calls result.
FIG. 8 presents in tabular form the calls represented graphically in FIG. 7. FIG. 8 reveals that every call conflicts with every other call at exactly one port—either input or output. If any one port is changed, then the call for which the port has changed ceases to conflict with at least one other call in the set, leading to a smaller number of colors for graph coloring. No ports can be added to any call to create a greater degree of coloring difficulty, since all calls are already 2-cast. The set is therefore a maximal clique for 2-cast in the sense that it requires the most colors for the fewest number of calls for any set of 2-cast calls. This difficult case can be repeated many times to create a difficult 100% load. Since the clique uses each referenced port twice, the clique can be repeated m/2 times in which case every call will conflict with every other call and require a minimum of 4 m/2 or 2m colors or timeslots for scheduling.
Maximal cliques can also be formed for 3-cast and 4-cast. In the case of 3-cast, each port is referenced 3 times, meaning the clique can be repeated m/3 times. This leads to a set of calls with a minimal coloring of 3m (9 calls with m/3 repetitions for a minimum coloring of 3m). FIG. 9 tabulates a maximal clique for 3-cast consisting of the set of nine connection requests A:(1→4, 5, 6), B:(1→7, 8, 9), C:(1→10, 11, 12), D:(2→4, 7, 10), E:(2→5, 8, 11), F:(2→6, 9, 12), G:(3→4, 8, 12), H:(3→5, 9, 10) and I:(3→6, 7, 11). Every call conflicts with every other call at exactly one port.
In the 4-cast case, each port is referenced 4 times and there are 16 calls which can be repeated m/4 times leading to a minimal coloring of 4m (16 calls with m/4 repetitions for a minimum coloring of 4m). FIG. 10 tabulates the resultant maximal clique, again revealing that every call conflicts with every other call at exactly one port.
It is accordingly apparent that maximal cliques for 2-cast, 3-cast and 4-cast connection schedules involving m timeslots can be formed, as above, with minimal colorings of 2m, 3m, and 4m respectively. However, although a maximal clique establishes the minimum number of colors required to color the corresponding graph, a maximal clique does not establish the maximum number of colors required to color all graphs. For example, as previously explained with reference to FIG. 4, worst case strictly non-blocking 2-cast scheduling with m timeslots leaves 3m−3 timeslots free. This is equivalent to saying that the theoretical maximum coloring of a graph representing 2-cast scheduling with m timeslots is 3m−3. The 3-cast clique's minimal coloring of 3m thus exceeds the theoretical maximum possible coloring for 2-cast. This implies that, regardless of the theoretical possibility that there could be a set of 2-cast call requests which is more difficult to schedule than the set represented by the 2-cast clique, the set represented by the 3-cast clique presents an even greater scheduling challenge. It is accordingly appropriate to adopt a set of call requests represented by a maximal clique of size N+1 as being representative of a worst case scheduling challenge for N-cast. This invention addresses that challenge.